package com.xiongda;

import java.util.*;

public class LeetCode126 {
    class Solution {
        List<List<String>> result;
        List<Set<Integer>> map;
        List<List<Integer>> next;
        List<Integer> temp = new LinkedList<Integer>();
        int begin, end;
        List<String> wordList;

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            wordList.add(beginWord);
//			Collections.sort(wordList);
            this.wordList = wordList;
            result = new LinkedList<List<String>>();
            map = new LinkedList<Set<Integer>>();
            next = new LinkedList<List<Integer>>();
            for (int i = 0; i < wordList.size(); i++) {
                map.add(new HashSet<Integer>());
                next.add(new LinkedList<Integer>());

            }
            Iterator<String> it1 = wordList.iterator();

            for (int i = 0; i < wordList.size(); i++) {
                Iterator<String> it2 = wordList.iterator();
                String string1 = it1.next();
                if (string1.equals(beginWord))
                    begin = i;
                if (string1.equals(endWord))
                    end = i;
                for (int j = 0; j < wordList.size(); j++) {

                    String string2 = it2.next();
                    if (match(string1, string2))
                        map.get(i).add(j);
                }
            }
//			System.out.println(map);
            Set<Integer> set = new HashSet<>();
            boolean[] visited = new boolean[wordList.size()];
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.add(begin);
            visited[begin] = true;
            while (!visited[end]) {
                while (!queue.isEmpty()) {
                    Integer now = queue.poll();
                    for (Integer integer : map.get(now))
                        if (!visited[integer]) {
                            set.add(integer);
                            next.get(now).add(integer);
//							System.out.println(now + " " + integer);
                        }
                }
                queue.addAll(set);
//				System.out.println(set);
                for (Integer integer : set)
                    visited[integer] = true;
                set.clear();
            }

            getResult(begin);
            return result;
        }

        private boolean match(String string1, String string2) {
            int missCount = 0;
            for (int i = 0; i < string1.length(); i++)
                if (string1.charAt(i) != string2.charAt(i))
                    missCount++;
            return missCount == 1;
        }

        private LinkedList<String> changeInt2Str() {
            LinkedList<String> ls = new LinkedList<String>();
            for (Integer integer : temp) {
                ls.add(wordList.get(integer));
            }
            return ls;
        }

        private void getResult(int now) {
            temp.add(now);
            if (now == end)
                result.add(changeInt2Str());
            else
                for (Integer integer : next.get(now))
                    getResult(integer);
            ((LinkedList<Integer>) temp).removeLast();
        }

    }

    public static void main(String[] args) {
        String beginWord = new String("hit");
        String endWord = new String("cog");
        List<String> list = new LinkedList<String>(Arrays.asList("hot", "dot", "dog", "lot", "log", "cog"));

        List<List<String>> result = new LeetCode126().new Solution().findLadders(beginWord, endWord, list);
        System.out.println(result);

    }
}
